package com.bloom.demo.bit;

import java.util.BitSet;

/**
 * 布隆过滤器
 *
 * @author Amadeus
 * @date 2025/01/14
 */
public class BloomFilter {

    /**
     * 位数组
     */
    private BitSet bitSet;

    /**
     * 位数组大小
     */
    private int size;

    /**
     * hash种子
     */
    private int[] seeds;

    /**
     * 构造函数
     * 初始化位数组和哈希种子
     *
     * @param size      大小
     * @param hashCount 哈希计数
     */
    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.bitSet = new BitSet(size);
        this.seeds = new int[hashCount];
        for (int i = 0; i < hashCount; i++) {
            // 简单设置种子
            seeds[i] = i + 1;
        }
    }

    private int hash(String value, int seed) {
        int result = 0;
        for (char c : value.toCharArray()) {
            result = seed * result + c;
        }
        return Math.abs(result % size);
    }

    public void add(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            bitSet.set(hash, true);
        }
    }

    /**
     * 判断是否存在
     * 对所有种子进行hash，并判断对应位置是否为1
     * 全部为1则大概率存在
     * 全部为0则一定不存在
     *
     * @param value 价值
     * @return boolean
     */
    public boolean contains(String value) {
        for (int seed : seeds) {
            int hash = hash(value, seed);
            // 有一个不匹配就返回false
            return bitSet.get(hash);
        }
        return true;
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1000, 5); // 创建布隆过滤器，大小1000，5个哈希函数

        bloomFilter.add("hello");
        bloomFilter.add("world");

        System.out.println(bloomFilter.contains("hello")); // 输出true
        System.out.println(bloomFilter.contains("world")); // 输出true
        System.out.println(bloomFilter.contains("java")); // 输出false（可能为false）
    }

}
